package main.java.data_structure;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Wrb
 * @date 2019/6/10 14:32
 */

//由于key需要进行比较，所以需要继承Comparable
public class BST<Key extends Comparable<Key>, Value> {

	// 树中的节点为私有的类，外界不需要了解二分搜索树节点的具体实现
	private class Node {
		private Key key;
		private Value value;
		private Node left, right;

		public Node(Key key, Value value) {
			this.key = key;
			this.value = value;
			left = right = null;
		}

		public Node(Node node){
			this.key = node.key;
			this.value = node.value;
			this.left = node.left;
			this.right = node.right;
		}
	}

	private Node root;
	private int count;

	public BST() {
		root = null;
		count = 0;
	}

	public int size() {
		return count;
	}

	public boolean isEmpty() {
		return count == 0;
	}

	public void insert(Key key, Value value) {
		root = insert(root, key, value);
	}

	private Node insert(Node node, Key key, Value value) {
		if (node == null) {
			count++;
			return new Node(key, value);
		}

		if (key.compareTo(node.key) == 0) {
			node.value = value;
		} else if (key.compareTo(node.key) < 0) {
			node.left = insert(node.left, key, value);
		} else {
			node.right = insert(node.right, key, value);
		}

		return node;
	}

	//非递归实现
	public Node insertNode(Key key, Value value) {
		Node node = root;
		while (true) {
			if (node == null) {
				count++;
				node = new Node(key, value);
				break;
			}
			if (key.compareTo(node.key) == 0) {
				node.value = value;
				break;
			} else if (key.compareTo(node.key) < 0) {
				node = node.left;
			} else {
				node = node.right;
			}
		}
		return node;
	}

	public boolean contain(Key key) {
		return contain(root, key);
	}

	private boolean contain(Node node, Key key) {
		if (node == null) {
			return false;
		}

		if (key.compareTo(node.key) == 0) {
			return true;
		} else if (key.compareTo(node.key) < 0) {
			return contain(node.left, key);
		} else {
			return contain(node.right, key);
		}
	}

	public Value search(Key key) {
		return search(root, key);
	}

	private Value search(Node node, Key key) {
		if (node == null) {
			return null;
		}
		if (key.compareTo(node.key) == 0) {
			return node.value;
		} else if (key.compareTo(node.key) < 0) {
			return search(node.left, key);
		} else {
			return search(node.right, key);
		}
	}
	//递归前序遍历 （深度优先遍历）
	public void preOrder(Node node) {
		if (node != null) {
			System.out.print(node.key + " ");
			preOrder(node.left);
			preOrder(node.right);
		}
	}
	//递归中序遍历 （深度优先遍历）（对于二叉搜索树，遍历有序）
	public void inOrder(Node node) {
		if (node != null) {
			inOrder(node.left);
			System.out.print(node.key + " ");
			inOrder(node.right);
		}
	}
	//递归后序遍历 （深度优先遍历）
	public void postOrder(Node node) {
		if (node != null) {
			postOrder(node.left);
			postOrder(node.right);
			System.out.print(node.key + " ");
		}
	}

	//层序遍历 （广度优先遍历）
	public void levelOrder() {
		Queue<Node> q = new LinkedList<Node>();
		q.add(root);
		while (!q.isEmpty()) {
			Node node = q.remove();

			System.out.println(node.key);

			if( node.left != null )
				q.add( node.left );
			if( node.right != null )
				q.add( node.right );
		}
	}

	//最小键值
	public Key miniMum() {
		assert count != 0;
		Node minNode = minimum( root );
		return minNode.key;
	}

	private Node minimum(Node node) {
		if (node.left == null) {
			return node;
		}
		return minimum(node.left);
	}

	// 寻找二分搜索树的最大的键值
	public Key maximum(){
		assert count != 0;
		Node maxNode = maximum(root);
		return maxNode.key;
	}

	private Node maximum(Node node) {
		if (node.right == null) {
			return node;
		}
		return minimum(node.right);
	}

	public void removeMin() {
		if (root != null) {
			root = removeMin(root);
		}

	}

	private Node removeMin(Node node) {
		if (node.left == null) {
			Node rightNode = node.right;
			node.right = null;
			count --;
			return rightNode;
		}
		node.left = removeMin(node.left);
		return node;
	}

	public void removeMax() {
		if (root != null) {
			root = removeMax(root);
		}
	}

	private Node removeMax(Node node) {
		if (node.right == null) {
			Node leftNode = node.left;
			node.left = null;
			count --;
			return leftNode;
		}
		node.right = removeMax(node.right);
		return node;
	}

	//hubbard deletion 待删除节点的右子树的最小值替代待删除节点
	// (右子树的最小值可看做待删除节点的后继，我们也可以用前驱来代替（左子树的最大值）)

	// 从二分搜索树中删除键值为key的节点
	public void remove(Key key) {
		remove(root, key);
	}

	private Node remove(Node node, Key key) {
		if(node == null){
			return null;
		}
		if (key.compareTo(node.key) < 0) {
			node.left = remove(node.left,key);
			return node;
		} else if (key.compareTo(node.key) > 0) {
			node.right = remove(node.right, key);
			return node;
		}else {
			//key == node.key
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				count --;
				return rightNode;
			}
			if (node.right == null) {
				Node leftNode = node.left;
				node.left = null;
				count --;
				return leftNode;
			}
			//左右孩子都不为空

			// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
			// 用这个节点顶替待删除节点的位置
			Node successor = new Node(minimum(node.right));
			count ++;

			successor.right = removeMin(node.right);
			successor.left = node.left;

			node.left = node.right = null;
			count --;

			return successor;
		}
	}

	// 在以node为根的二叉搜索树中, 寻找key的floor值所处的节点, 递归算法
	private Node floor(Node node, Key key){

		if( node == null )
			return null;

		// 如果node的key值和要寻找的key值相等
		// 则node本身就是key的floor节点
		if( node.key.compareTo(key) == 0 )
			return node;

		// 如果node的key值比要寻找的key值大
		// 则要寻找的key的floor节点一定在node的左子树中
		if( node.key.compareTo(key) > 0 )
			return floor( node.left , key );

		// 如果node->key < key
		// 则node有可能是key的floor节点, 也有可能不是(存在比node->key大但是小于key的其余节点)
		// 需要尝试向node的右子树寻找一下
		Node tempNode = floor( node.right , key );
		if( tempNode != null )
			return tempNode;

		return node;
	}


	// 在以node为根的二叉搜索树中, 寻找key的ceil值所处的节点, 递归算法
	public Node ceil(Node node, Key key){

		if( node == null )
			return null;

		// 如果node的key值和要寻找的key值相等
		// 则node本身就是key的ceil节点
		if( node.key.compareTo(key) == 0 )
			return node;

		// 如果node的key值比要寻找的key值小
		// 则要寻找的key的ceil节点一定在node的右子树中
		if( node.key.compareTo(key) < 0 )
			return ceil( node.right , key );

		// 如果node->key > key
		// 则node有可能是key的ceil节点, 也有可能不是(存在比node->key小但是大于key的其余节点)
		// 需要尝试向node的左子树寻找一下
		Node tempNode = ceil( node.left , key );
		if( tempNode != null )
			return tempNode;

		return node;
	}
}
